\documentclass[fancyhdr,a4paper,10pt]{report}
\usepackage[frenchb]{babel}
\usepackage[utf8x]{inputenc}

\usepackage[pdftex,bookmarks,colorlinks]{hyperref}
\usepackage{graphicx}

\hypersetup{linkcolor=black,urlcolor=black}

\usepackage{fancyhdr}
\lhead{}
\chead{}
\rhead{}
\lfoot{Christopher Glass}
\cfoot{}
\rfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}


\pagestyle{fancy}
\addtolength{\topmargin}{-15mm}
\addtolength{\oddsidemargin}{-5mm}
%\addtolength{\evensidemargin}{-30mm}
\setlength{\textheight}{240mm}
\setlength{\textwidth}{140mm}

\makeatletter
\def\maketitle{%
  \null
  \thispagestyle{empty}%
  \vfill
  \begin{center}\leavevmode
    \normalfont
    {\LARGE \textbf{\@title}\par}%
    \vskip 0.5cm
    {\LARGE (Pré-étude)\par}%    
    \vskip 2cm
    {\Large \textbf{\@author}\par}%
    {\normalsize Etudiant en emploi, travaillant chez VMware Switzerland Sàrl.\par}%
    \vskip 1cm
    {\normalsize \textbf{Mandant:}\par Ingénieurs du Monde, Sous la direction du Dr. François Ullmann\par}%
    \vskip 0.5cm
    {\normalsize \textbf{Conseiller:}\par Dr. Eytan Zysman\par}%
    \vskip 10cm
    {\normalsize \@date\par}%
  \end{center}%
  \vfill
  \null
  \cleardoublepage
  }
\makeatother

\title{Système de cache HTTP distribué pour réseaux informatiques maillés, instables, et à forts temps de latence.}
\author{Christopher Glass}
\date{\today}


\begin{document}

\maketitle

\tableofcontents

% *** INTRODUCTION
\chapter[Introduction]{Introduction}
\section[Contexte]{Contexte}

Dans les pays émergeants, un des principaux obstacles au déploiement de l'internet est le coût prohibitif des infrastructures fondamentales de liens point-à-point\footnote{Les liens points-à-points relient entre eux deux interlocuteurs uniques} entre les différentes parties du pays.\\
En effet, déployer un réseau de type occidental requiert d'installer des câbles de fibre optique sur de longues distances, qui le plus souvent sont faiblement peuplées, et qui potentiellement traversent des terrains inhospitaliers (chaînes montagneuses, déserts \ldots).\\

Partant de ce constat, j'ai entrepris d'évaluer une solution logicielle pour améliorer la qualité du réseau internet dans des régions faiblement peuplées. Soumis à Ingénieurs du Monde, le projet a suscité un grand enthousiasme, ce qui m'a encouragé à le réaliser dans le cadre de mon travail de diplôme.

\subsection[Ingénieurs du Monde]{Ingénieurs du Monde}

Ingénieurs du Monde (IdM), est une organisation non-gouvernementale enregistrée et représentée auprès de l'organisation des nations unies dont la vocation est d'améliorer le bien-être et le développement des pays émergeants et des régions en voie de développement\footnote{Vous pouvez trouver de plus amples informations sur leur site internet cité en webographie (Section \ref{cha:webo})}.\\

Notemment présent en Afrique, IdM sponsorise plusieures écoles techniques, notamment en Tanzanie, connectées à l'internet ou pas, qui bénéficieront directement de la mise en place d'un réseau de caches internet \footnote{Cache est ici utilisé dans son sens ``réserve temporaire'' - Voir glossaire (\ref{cha:gloss})} autant par l'utilisation de celui-ci que par l'acquisition de connaissances apportées sous forme de documentation.

\subsection[Réseaux hertziens]{L'avantage des réseaux hertziens}
Bien que déployer de l'infrastructure câblée soit généralement trop coûteux, le déploiement d'antennes-relais pour une infrastructure internet est comparativement abordable.\\
Les antennes, particulièrement en terrain inhospitalier, posent cependant problème: leur taux moyen de panne est bien plus élevé, de par la nature des antennes exposées et de leur sensibilité face aux éléments (pluie, neige, tempêtes de sable, chaleur excessive, nuages de sauterelles \ldots). 

Dans ce contexte, un système distribué habituel ne fonctionne que très mal: les caches habituels partent du principe que bien que la bande passante\footnote{Bande passante: Quantité d'information transmissible dans un temps donné. Voir glossaire (\ref{cha:gloss})} soit limitée, les temps de latence\footnote{Temps que met l'information à parcourir un aller-retour entre deux interlocuteurs - Voir glossaire (\ref{cha:gloss})} sont bas et les noeuds généralement disponibles. Pour un déploiement dans un milieu inhospitalier, la probabilité que la bande-passante soit le goulot d'étranglement diminue considérablement.

\paragraph{Réseaux point-à-points}
Le logiciel de cache distribué présenté amoindrit ce problème: 
\begin{itemize}
\item L'information est distribuée le long des noeuds
\item Il est possible de paramétrer le niveau de récursion\footnote{Profondeur d'exploration de l'arbre recouvrant ayant N pour sommet. Voir glossaire (\ref{cha:gloss})}. 
\end{itemize}

Un unique lien composé de plusieurs caches ``en série'' distribue l'information au sein de chaque noeud, et ainsi tire profit de la somme des ressources \emph{hardware} qui le compose.

\paragraph{Réseaux maillés}
Le réseau maillé est plus intéressant, car chaque noeud possède plusieurs liens vers des noeuds alentours.\\ Chacun des noeuds profite ainsi de la "proximité" relative de ses voisins pour aller y chercher, à moindre coût, les informations demandées par ses utilisateurs. Partant du postulat que les sites auxquels on accède sont globalement les mêmes (Wikipedia ou Google par exemple, seront vraisemblablement consultés dans plusieurs écoles voisines avec une haute fréquence), la proximité des noeuds, au sens ``nombre de liens à parcourir'', collabore à la qualité du service internet proposé aux utilisateurs.

\subsection[Coût peu élevé des antennes directionnelles]{Coût peu élevé des antennes directionnelles}

Les antennes directionnelles sont vastement disponibles, à faible coût. \\ En effet, les antennes réceptrices de signaux satellites sont peu coûteuses, et du mode de vie occidental découle qu'une grande quantité de ces antennes finissent chaque année dans des centres de recyclage, au mieux, ou dans des décharges, au pire.\\

Se servir de ces antennes de récupération permet donc de fabriquer des antennes WiFi directionnelles efficaces et a coût raisonnable. Le site \mbox{\url{www.weijand.nl}} propose par exemple une solution dont le coût est inférieur à 10 Euros (Voir webographie en Section \ref{cha:webo}).

\subsection[Grande disponibilité des antennes GSM]{Grande disponibilité d'antennes GSM}

Dans le monde, les réseaux téléphoniques sont fortement disséminés. Même dans les pays en voie de développement, bien que le niveau de vie moyen soit largement moins élevé que dans les pays occidentaux, les téléphones cellulaires sont très répandus.\\

Il est donc logique, dans une optique de distribution de connections internet, de tirer parti des infrastructures existantes afin d'amoindrir les coûts au maximum.\\

Il est tout a fait possible, voir facile, de coupler un module GPRS à un ordinateur a portée de réception d'une antenne téléphonique, et de créer à partir de celui-ci un réseau WiFi, directionnel ou pas, afin de distribuer plus avant la connection internet ainsi rendue disponible. \\

Dans la mesure ou le système de cache distribué décrit dans ce texte est indifférent au mode de transmission ou de routage, il est trivial d'en installer une copie sur l'ordinateur, devenu ``gateway''\footnote{Un noeud d'un réseau équipé pour s'interfacer avec un autre réseau, éventuellement en utilisant un protocole différent. Voir glossaire chapitre \ref{cha:gloss}} internet, et de configurer les caches des noeuds voisins pour le considérer comme un cache pair. Il peut, de plus, fournir un point de routage vers le réseau internet externe. Un réseau maillé configuré avec un protocole intelligent (de type OSPF\footnote{\emph{Open Shortest Path First} - Voir glossaire chapitre \ref{cha:gloss}} par exemple), peut tirer parti d'un tel système de routage.


% *** SOLUTIONS ALTERNATIVES
\section[Solutions alternatives]{Solutions alternatives}

Une question valable que l'on peut se poser en lisant ce document est ``pourquoi ne pas simplement utiliser le logiciel de cache X, qui existe déjà?''. Il existe plusieures rasions à cela:\\
%Les inconvénients décrits sont données par rapport au contexte spécifique de ce travail: Déployer ledit cache dans un réseau instable, à fort temps de latence.

\subsection[Squid]{Squid}
Le plus célèbre des logiciels de cache.\\
Squid est un logiciel \emph{libre} de cache HTTP très complet, permettant de répondre efficacement à beaucoup de scénarios d'utilisation. Plus d'informations sur Squid peut être obtenue en consultant leur site web cité en Webographie (Section \ref{cha:webo}).
\paragraph{Avantages}
\begin{itemize}
\item Cache de contenu pour une utilisation locale. Squid permet de \emph{mettre en cache} des objets HTTP pour une utilisation locale, c'est à dire dans le même type de configuration que le logiciel présenté, ou un grand nombre d'utilisateurs accèdent à des sites similaires, et où Squid sert le contenu le plus statique (images, scripts, pages html) depuis son \emph{cache} local plutôt que d'aller chercher l'information sur le site distant à chaque fois.
\item Cache de contenu local pour une utilisation distante. Squid permet de mettre en cache des données d'un serveur web local sur d'autres machines locales exposées à l'internet, afin de répartir la charge web. Cette configuration permet de ne pas surcharger le serveur web local tout en garantissant aux utilisateurs externes des temps de réponse raisonnables. En effet, les serveurs Squid absorbent une majorité des demandes, et n'envoient au ``vrai'' serveur web que les requêtes qu'ils n'arrivent pas a traiter. C'est le mode d'utilisation que les grand sites font de Squid (par exemple Wikipedia, Amazon.com).\\
\end{itemize}

\paragraph{Inconvénients}
\begin{itemize}
\item Structure hiérarchique. Bien que Squid puisse fonctionner dans une configuration ``réseau de caches'', il n'est capable que d'établir des relations hiérarchiques entre caches, non des relations de type ``pairs''. Ainsi, dans un réseau maillé, il serait indispensable de segmenter le réseau en plusieures sous-réseaux de caches indépendants, et surtout, il faudrait définir un cache ``père'' auquel tout les caches ``fils'' vont demander l'information quand ils ne l'ont pas ou qu'elle n'est pas considérée assez ``fraîche''\footnote{La fraîcheur dans ce contexte, désigne l'actualité d'un fichier. Un fichier ``frais'' est un fichier dont on considère le contenu comme actuel.}. Dans un réseau instable, il est fort dangereux de créer des points de pannes critiques - si un seul ``père'' tombe en panne, tout le sous-réseau de cache est alors inutilisable.
\item Protocole spécialisé. Squid utilise un protocole spécialisé pour synchroniser les caches entre eux. Cela a bien sûr l'avantage de garantir des données plus fraîches, mais aussi l'échange de statistiques sur les objets les plus demandés afin de les répartir de façon plus efficace. En revanche, Squid part du principe que les temps de latence sont très faibles, et réduit un maximum l'utilisation de la bande-passante. C'est tout a fait logique: Squid est conçu pour des réseaux occidentaux, où la latence est minime (les réseaux sont très souvent en fibre optiques), et dans le cas d'un cache de contenu pour utilisateurs distants, il est normal de vouloir minimiser la bande-passante utilisée - c'est justement pour cela que Squid a été déployé!
\item Difficulté d'apprentissage. Bien que le code source de Squid soit disponible, sa taille, ainsi que le langage de programmation utilisé rendent l'apprentissage de son fonctionnement interne difficile. La configuration d'un cache Squid est elle-même peu aisée, particulièrement dans le cas de réseaux de caches.
\end{itemize}

\subsection[Dijjer]{Dijjer}
Dijjer utilise le protocole bittorrent\footnote{Le protocole bittorrent est généralement utilisé pour distribuer de gros fichiers à un grand nombre de gens. Voir Glossaire, section \ref{cha:gloss}} de façon très astucieuse en l'appliquant aux caches Web. Presque entièrement décentralisé, Dijjer propose à ses utilisateurs de mettre en cache sur leurs machines le contenu internet qu'ils obtiennent durant la navigation Internet\footnote{Les navigateurs Web mettent en cache une grande quatité de données automatiquement.}, puis de mettre les utilisateurs en relation à travers le protocole bittorrent, avec lequel ils mettent en commun les données qu'ils ont accumulés.\\ Plus d'information sur Dijjer peut être obtenue en consultant le site web cité en Webographie (Section \ref{cha:webo}).

\paragraph{Avantages}

\begin{itemize}
\item Sauvegarde de la bande-passante. Dijjer est a été immaginé pour conserver au maximum la bande passante des utilisateurs.
\item Mise en relation automatique des caches. Les caches Dijjer utilisent le protocole Bittorrent: une machine centrale met les caches en relation, afin de créer un énorme réseau d'utilisateurs qui partagent mutuellement leurs données \emph{via} bittorrent. Si du contenu est disponible sur d'autre caches, Dijjer va alors télécharger le contenu, morceau par morceau, depuis la machine de \emph{plusieurs utilisateurs à la fois}. Le gain de temps est énorme, et de plus, le fait que le site distant ``original'' soit disponible ou pas n'a aucune importance (il n'est parfois pas sollicité du tout!).
\item Contenu distribué. Chaque machine n'utilise pas plus d'espace disque qu'habituellement - les navigateurs modernes mettent déjà automatiquement en cache le contenu affiché. Dijjer se contente de mettre en commun ce cache.
\end{itemize}

\paragraph{Inconvénients}
\begin{itemize}
\item Centralisé. Bien que faiblement centralisé, Dijjer dépend d'un \emph{tracker} central. Ne pas pouvoir atteindre ce serveur central implique une connectivité avec les autres caches fortement réduite, voir impossible.
\item Fort nombre de requêtes. Le protocole BitTorrent a été immaginé pour distribuer de gros fichiers de façon efficace, sur des réseaux de type occidentaux (au pire, composés de connections de type DSL). Les temps de latence étant en général négligeables, Dijjer est très bavard, même si la quantité d'information échangée à chaque fois est négligeable. Dans un réseau à forte latence, ce bavardage incessant avec les autres caches entraînerai un fort ralentissement du réseau pour tous les utilisateurs, et conduirait à un taux de pannes généralement plus élevé.
\item Plus maintenu. Dijjer est pour l'instant ``orphelin'' dans la mesure ou son développeur principal n'a apparemment plus le temps de le maintenir (en date du 1er Juin 2009). L'évolution et la survie du projet n'est donc pas garantie.
\end{itemize}

\subsection[Cache IP]{Caches IP}
Sous cette appellation générique, nous considérerons les caches de couche ISO 3 - les caches fonctionnant au niveau de la trame TCP/IP. Ces caches fonctionnent en cachant les transactions TCP entre deux ordinateurs. Bien que compatibles avec la solutions proposée, les caches TCP sont efficaces pour un lien unique, mais ne sont pas distribués. \\

En effet, il est illogique de distribuer du cache de trames TCP/IP, dans la mesure ou les demandes (\emph{lookups}) cache et leurs réponses sont elle-mêmes des trames TCP/IP! Une simple demande, fructueuse ou pas, entraînerai un nombre immense d'envoi de trames TCP/IP, qui elles-mêmes feraient l'objet de demandes de cache, qui à leur tour entraîneraient un nouvel envoi massif de requêtes, ainsi de suite \ldots

%En effet les informations contenues dans la trame (source, destination) suffisent pour les rendre uniques, il n'est donc pas intéressant de %les cacher. Pour que le cache distribué soit intéressant, il faudrait, pour chaque trame, lui retirer ses informations de source et de %destination. Cette opération est relativement coûteuse en temps processeur.\\
%Les caches IP ``rapides'' sont généralement des machines spécialisées, coûteuses.

% *** OBJECTIFS
\chapter[Objectifs]{Objectifs}

\section[Objectif principal]{Objectif principal}

L'objectif principal de ce travail est de fournir une ``brique de base'' pour permettre un déploiement à grande échelle, dans un pays en voie de développement, d'un réseau internet a faible coût: un logiciel de cache HTTP distribué pour réseaux instables et à forts temps de latence.
\\
Le cache proposé aura en outre les qualités suivantes:
\begin{description}
\label{cha:cdc}
\item [Persistance] Il est nécessaire, étant donnée la fréquence des pannes dans l'environnement de déploiement envisagé, qu'une remise en service d'un noeud de le laisse pas ``vide'' de contenu, afin qu'il puisse immédiatement contribuer aux caches voisins.
\item [Efficacité] Le logiciel proposé devra être peu demandant en ressources physiques, telles que temps processeur ou quantité de mémoire (vive ou de stockage) nécessaire a son opération.
\item [Vitesse] Le but d'un cache est de réduire le temps nécessaire a l'affichage d'une page internet; le logiciel présenté ne devra en aucun cas le ralentir.
\item [Documentation] Dans la mesure où ce cache est destiné à être déployé dans des pays en voie de développement, on veillera à ce que la qualité de la documentation soit exemplaire, afin de faciliter le transfert de connaissances à des techniciens locaux.
\end{description}

\section[Objectifs secondaires]{Objectifs secondaires}
\begin{description}
\item [Stockage diversifié] Dans le but de permettre une plus grande flexibilité sur les sites de déploiement, le cache pourrait, de plus, offrir la possibilité de profiter d'éventuels systèmes de stockage externes (bases de données déjà existante, systèmes de fichiers).\\

\item [Auto-configuration] Il serait intéressant de faciliter la configuration du cache quand il se trouve en présence d'un système de routage ``intelligent'', de type OSPF. Ce protocole de routage permet en effet d'avoir une liste de noeuds voisins, dans la mesure ou ce protocole la dresse déjà.

\item [Generation de statistiques] Il serait pratique pour la configuration de caches ulterieurs de pouvoir extraire des statistiques sur l'utilisation du cache: niveau de récursion moyen des requêtes, proportion de contenu servi depuis le cache, sites / pages / objets les plus consultés, type d'objets les plus demandés\ldots
\end{description}

\section[Facteurs de risque]{Facteurs de risque}
\subsection[Risque principal]{Risque principal}
Le risque principal dans la réalisation de ce logiciel est que les temps de réponse mesurés soient finalement, malgré une optimisation rigoureuse, plus longs que la requête originale sans cache.
\subsection[Risque secondaire]{Risque secondaire}
Un autre problème potentiel est que l'algorithme de parcours de graphe utilisé surcharge le réseau par un nombre d'appels récursifs trop grand. La détection et la correction des boucles est donc une priorité.



% *** CAHIER DES CHARGES
\chapter[Cahier des charges détaillé]{Cahier des charges détaillé}
\section[Livrables]{Livrables}

\subsection[Logiciel]{Logiciel}
La solution logicielle sera livrée sous la forme d'un CD contenant l'intégralité du code source de l'application, les binaires (le cas échéant), ainsi que tout autre fichier nécessaire au déploiement de ladite application.

\subsection[Documentation]{Documentation}
La documentation sera livrée en deux parties: une partie contenue dans le code source lui-même sous forme de commentaires, et une partie sous forme d'un fichier séparé, le manuel d'utilisateur.\\

Le manuel d'utilisateur doit permettre l'installation de l'application, son opération et sa maintenance sans aide externe. Les outils, librairies ou documents externes utilisés par l'application seront inclus, dans la mesure du possible et tant que leur licence de distribution le permet.

\section[Fonctions souhaitées]{Fonctions souhaitées}
\begin{description}
\label{section:fonctions}
\item[Facilité de déploiement] La documentation livrée doit permettre a un étudiant de premier cycle, non-programmeur mais familiarisé à la maintenance informatique, d'effectuer une installation complète sans autre aide que la documentation incluse.
\item [Distribution] Pour palier au problème des ressources disponibles, le cache sera distribué. Il devra néanmoins pouvoir fonctionner si aucun voisin n'est disponible.
\item[Persistance] Dans le cas d'une coupure de courant aléatoire, le cache doit, au redémarrage de la machine, se trouver dans le même état qu'avant celle-ci. Ceci implique que les données soient écrites de façon transactionnelle: soit dans une base de données, soit dans un système de fichier journalisé.
\item[Configuration] Le logiciel devra être configurable. On voudrait en particulier configurer: Les noeuds voisins, La quantité de mémoire vive allouée au cache, l'espace disque maximum a utiliser.
\item[Filtrage des ressources] On doit pouvoir filtrer les objets a mettre en cache, ainsi que le temps que chacun devra rester en cache.
\item[Détection de boucles] Le système devra être capable de détecter le plus vite possible les boucles réseaux qu'il crée (si il en crée), et régler le problème automatiquement, y compris en cas de mauvaise configuration par l'utilisateur.
\end{description}

\section[Contraintes]{Contraintes}

\begin{description}
\label{section:contraintes}
\item[Language] La documentation et le code source devront être écrits en Anglais.
\item[Vitesse d'exécution] La vitesse d'exécution du logiciel, y-compris les requêtes sur les caches voisins et le retour de l'information de devront jamais dépasser le temps mesuré que met une requête, depuis un noeud donné, à obtenir l'information demandée depuis son serveur d'origine.
\item[Utilisation des ressources] Les ressources disponibles dans les pays émergeant sont bien moindres que celles dont nous avons l'habitude. L'application devra pouvoir fonctionner sur une machine de type Pentium (500Mhz), avec 128Mb de mémoire vive, et un espace disque de 256Mb dédié aux données. Le choix du système d'exploitation étant déterminant, on privilégiera une plate-forme \emph{libre}, largement moins exigeante en ressources.
\item[Liberté] Le logiciel sera distribué sous licence GPLv3 selon les souhaits du mandant. Il est donc impératif que la licence en question soit respectée dans sont intégralité.
\end{description}

% *** ENVIRONMENT DE TRAVAIL PRÉVU
\chapter[Environnement de travail prévu]{Environnement de travail prévu}
%\section[Outils]{Outils}
%Les outils de développment nécessaires
\section[Matériel et outils]{Matériel et outils}
Aucun matériel spécifique n'est requis à l'exception du matériel habituel nécessaire a un programmeur (Ordinateur fonctionnel).\\
Les outils nécessaires sont: un outil d'édition de code source, un compilateur (ou un interprèteur le cas échéant), et une machine de déployement. L'intégralité des outils sont displonibles en tant que logiciels libres pour n'importe quel système d'exploitation, le choix de ces derniers est donc peu significatif.\\
Le code source sera sauvegardé sur un système de gestion des sources, déjà existant et disponible (le présent document y est également sauvegardé).

\section[Logiciel]{Logiciel}
\subsection[Langage de programmation]{Langage de programmation}
Le choix se porte sur le Python, parce qu'il présente un certain nombre d'avantages intéressants:

\begin{description}

\item [Puissance:] Python est un langage de script \emph{orienté-objet} permettant la production de code concis et facile à comprendre. Il permet en outre d'enseigner la programmation de façon itérative, sans changer de langage: Commencer par de la programmation procédurale, puis retravailler le code pour le rendre \emph{orienté-objet}, puis finalement introduire des notions de programmation ``de haut niveau'' (récursion, \emph{lambda-fonctions}, introspection, programmation dynamique, programmation concurrente, algorithmes distribués, \emph{design patterns} \ldots).

\item [Syntaxe stricte:] Python considère l'indentation comme un élément lexical. Le code python de n'importe quel programmeur au monde est donc indenté et formatté de la même façon, ce qui facilite grandement la compréhension d'un programme pour quelqu'un ayant déjà eu affaire à Python. Avoir appris Python permet donc de contribuer très rapidement à des projets \emph{open-source}.

\item [``Batteries included'']\footnote{``Les piles sont livrées avec'' - la version Anglaise est conservée car il s'agit d'une devise.}: Python est fourni avec une librairie de fonctions et d'objets très vaste, et ne nécessite pas de faire appel à une ou des librairies externes pour une grande majorité de tâches. Ces concepteurs comparent ainsi Python à un appareil électronique dont les piles seraient vendues avec:  nul besoin d'effectuer un achat séparé, tout est livré!

\item [Vie active:] Python est le langage de programmation de choix d'une vaste communauté. Un grand nombre de sociétés de développement logiciel contribuent activement à son évolution et à sa maintenance (Google, Vmware, Apple, Microsoft, SUN, IBM). Beaucoup de projets \emph{open-source} sont écris en Python, il est donc facile de trouver des exemple, des sites communautaires d'échange de conseils, des \emph{blogs} spécialisés\ldots

\item [Multi-plateformes:] Python est pré installé sur de très nombreux systèmes d'exploitation (MacOS, les Linux, Solaris, les BSD), et il est disponible en télé chargement pour de nombreux autres (Windows, AS400, etc.).

\item [Extensible:] Bien qu'étant un language de scripting (donc comportant un coût d'\emph{overhead}\footnote{L'\emph{overhead} est une faible surconsommation de ressources, sacrifiées au profit d'un autre avantage (ici, la facilité de rédaction et de lecture du code). Voir glossaire Section \ref{cha:gloss}}), Python est aisément extensible et/ou optimisable avec C++, soit pour lui exposer une librairie non disponible dans la librairie standard, soit pour optimiser certains algorithmes \footnote{Il est possible de rendre ces algorithmes spécifiques a un type de processeur afin de tirer parti des possibilités \emph{hardware}, comme par exemple d'instructions spécialisées}

\item [Documenté:] Python est livré avec une documentation complète, et de nombreux tutoriaux de qualité exemplaire, faciles à comprendre et souvent pleins d'humour (ce qui facilite l'apprentissage).

\end{description}

\subsection[Système d'exploitation]{Système d'exploitation}
Le système d'exploitation de développement sera un système d'exploitation \emph{libre}. Pour sa facilité de mise en place et sa grande flexibilité, le choix se porte sur Ubuntu GNU/Linux.

\subsection[Base de données]{Base de données}
Plusieures solutions de stockage des données sont envisagées dans la planification, mais le logiciel devra dans tous les cas être capable de stocker ses données sur disque dur (afin de répondre à la partie ``persistance'' du cahier des charges, Section \ref{cha:cdc}).\\

La solution la plus immédiate pour ce faire est d'utiliser le système de base de données \emph{SQLite} (voir webographie, Section \ref{cha:webo}). Ce système offre plusieurs avantages particuliers, mais aussi certaines limitations décrites ci-après:\\

\paragraph{Avantages:}
\begin{itemize}
\item Publique. SQLite est distribuée comme faisant partie du domaine publique. Quiconque est donc libre de faire ce que bon lui semble avec le code source. Bien que n'étant pas en tant que tel \emph{libre}, SQLite offre certains des mêmes avantages qu'un logiciel \emph{libre}, à savoir la liberté d'en étudier le code source, et la liberté de le redistribuer, avec ou sans modifications. Le site web de SQLite est cité en webographie (Section \ref{cha:webo}).
\item Légère. Élaborée pour les systèmes embarqués, SQLite ne pèse que quelques ko sur disque.
\item Rapide. SQLite permet de traiter efficacement une grande quantité de données (plusieurs Terra octets).
\item Intégrée à Python. Les librairies d'accès à SQLite sont inclues dans la librairie de base de Python.
\item ACID. Les versions les plus récentes de SQLite satisfaisent les exigeances ACID\footnote{ACID est l'acronyme Anglais de \emph{Atomicity, Consistency, Isolation, Durability} (Voir Glossaire, Section \ref{cha:gloss})}
\end{itemize}
Ses points faibles sont les suivants:
\begin{itemize}
\item Externe. Il est nécessaire d'installer SQLite avant d'utiliser le programme de cache. SQLite est en revanche préinstallée dans une majorité de systèmes d'exploitation \emph{libres}, ce qui relativise ce désavantage.
\end{itemize}

\section[Banc de test]{Banc de test}
Il existe plusieurs façons de simuler le déploiement d'un système distribué. En voici une énumération, ainsi qu'un bref aperçu des avantages et des inconvénients pour chaque cas.

\subsection[Hôtes physiques]{Multiples hôtes physiques}
Il s'agit de la façon la plus intuitive de tester le déploiement d'un réseau informatique: en créer un ``in vivo''. La technique ici est ni plus ni moins que de créer un véritable réseau avec de vraies machines. Évidemment, cette possibilité nécessite un nombre potentiellement grand de machine physiques disponibles. Ce n'est malheureusement pas le cas dans le cadre de ce travail.

\subsection[Hôte unique, multiples instances]{Hôte unique, multiples instances}
Une autre façon de modéliser un réseau est de faire fonctionner plusieurs copies du logiciel en parallèle sur la même machine, sur des ports différents. Un désavantage certain de la méthode est que le temps de latence sera toujours proche de zéro, or ce travail de diplôme par du postulat que le temps de latence est élevé dans l'environment de déployement ciblé. Cette stratégie conviendrait donc mieux pour tester un système de cache conventionnel, où la latence est un problème moins primordial.

\subsection[Hôtes virtuels]{Multiples hôtes virtuels}
\label{subsec:virtuals}
La virtualization permet de modéliser à moindre coût un réseau de potentiellement grand. Chaque machine virtuelle possède son propre système d'exploitation, ce qui permet de modéliser des réseaux hétérogènes. Les performances globales peuvent être bridées, et la répartitions des ressources est garantie (par le fabriquant) d'être équitable. Un ralentissement impacterait donc toutes les machines à la fois, ce qui permet de tester l'efficacité de l'algorithme, la complexité restant la même bien que le temps mesuré soit fluctuant. Ainsi, la vitesse d'execution ralentit \emph{de façon uniforme} pour toutes les machines virtuelles.

\subsection[Solution hybride]{Solution hybride}
Une solution hybride consisterai en l'application de plusieures techniques sus-mentionnées à la fois: plusieurs hôtes physiques qui hébergerent chacun plusieures machines virtuelles qui elles-mêmes feont fonctionner plusieures copies du programme sur des ports différents, par exemple. Cette solution permet de créer des réseaux de test très complexes, ce qui semble disproportionné pour ce type de logiciel. De plus, bien que l'avantage de la taille soit certain, cette méthode cumule les désavantages des techniques utilisées.

\subsection[Solution retenue]{Solution retenue pour ce travail}
Pour ce travail en particulier, le choix se porte sur un système de test composé de multiples hôtes virtuels, comme décrit au point \ref{subsec:virtuals}. \\
Les multiples machines virtuelles, bien qu'entraînant un ralentissement du système en général, permet au moins de garantir une dégradation homogène des performances entre les différentes machines virtuelles, ce qui permet de mesurer la performance d'un point de vue objectif. Les performances réelles seront donc proportionnellement meilleures que celles mesurées dans les tests. \\
Finalement, cette solution permet de simuler de façon plus réaliste les conditions de déploiement réelles, à savoir les performances matérielles définies dans la cahier des charges (section \ref{section:contraintes}), en bridant les ressources allouées aux machines virtuelles pour qu'elles correspondent aux performances spécifiées.

% *** PLANIFICATION
\chapter[Planification]{Planification}

La méthodologie de planification sera la planification ``agile'' \footnote{Les méthodologies agiles sont un ensemble de méthodes permettant la planification et la réalisation de logiciels de façon efficace. Se référer à la bibliographie en chapitre \ref{cha:biblio} pour de plus ample informations}. Dans ce sens, le travail sera découpé en 9 itérations de 2 semaines. Les objectifs seront découpés selon cette méthode en ``\emph{User stories}'' \footnote{Les \emph{user stories} sont les unités de découpage du travail de base utilisées dans les méthodes agiles. Voir glossaire au chapitre \ref{cha:gloss}}, suivant les cas d'utilisation définis au préalable.

\section[Plan de travail détaillé]{Plan de travail détaillé}
\subsection[Cas d'utilisation]{Cas d'utilisation}
On distingue ici 3 cas d'utilisations, avec 3 acteurs:
\paragraph{L'utilisateur Humain}
C'est un humain qui utilise l'application, éventuellement sans le savoir. Il se contente d'envoyer des requêtes sur internet, qui sont interceptées par notre cache.
\paragraph{L'administrateur}
L'administrateur est un humain qui installe l'application de cache, la configure, et l'utilise. En ce sens, on peut dire qu'un administrateur \emph{étend} un utilisateur humain.
\paragraph{L'utilisateur cache voisin}
Cet utilisateur est un cache voisin qui envoie une demande de contenu, avec en header HTTP un niveau de récursion non null. Il est différent d'un utilisateur humain, car au cas ou la requête n'est pas en cache, il faut réduire le niveau de récursion. Dans le cas d'un utilisateur humain il faut en plus envoyer une requête au serveur final.


\subsection[Découpage du travail]{Découpage du travail}

Les user stories décrites englobent, comme le suggèrent les methodes agiles, le temps consacré à l'écriture du code, mais aussi le temps passé au test et à la documentation. Une user story n'est considérée comme ``finie'' que lors ce que le code, les tests et la documentation sont finis pour la fonctionalité décrite. Dans ce projet, selon le cahier des charges, la documentation d'une user story comprend la rédaction de la partie du manuel utilisateur correspondante.\\

Dans les methodes agiles de plannification, on utilise un unité abstraite, les \emph{story points} (ou ``Points'' en Français), qui sont généralement calculées pour chaque \emph{user story} à partir d'une tâche-étalon en proportion de la difficulté qu'une elle repésente par rapport à cet étalon. Une équipe de dévelopment choisit en général une tâche précédemment terminée dont toute l'équipe considère la difficulté comme faible.\\
Dans le cadre de ce travail en revanche, l'étalon utilisé pour déterminer les points sera le ``jour idéal'' de travail, unité généralement untilisée quand une équipe travaille ensemble pour la première fois, et qui donc n'a pas déjà effectué ensemble de tâche à utiliser comme étalon. Un jour idéal de travail représente une journée ``parfaite'', sans séances, et durant laquelle le programmeur peut travailler à cette unique tâche sans être interrompu par un événement exterieur. Naturellement, une telle journée est incroyablement rare dans une entreprise normal, mais l'étalon est néanmoins valide, puisqu'il est par nature commun aux membres de l'équipe. Ici, le ``jour idéal'' doit être compris comme ``soirée idéale'', puisque le travail sera effectué à temps partiel. \\
\begin{itemize}
\item Une soirée dure 4 heures.
\item Il y a 4 soirées par semaines.
\item Il y a 4 semaines par mois, donc 16 soirées idéales
\item Le travail s'étend sur 4 mois, il y a donc 64 soirées idéales.\\
%\item Le travail plannifié total représente donc environs 256 heures de travail ``idéales''.\\
\end{itemize}

Les heures de travail n'étant jamais idéales, le projet s'étendra donc logiquement sur une durée légèrement supérieure. Cette approche permet néanmoins d'estimer au fur et à mesure que le projet avance de la quantité de travail effectuée (en proportion), ainsi que la vitesse moyenne de progression. Cette vitesse est appelé \emph{vélocité} dans le ``jargon agile'', et sera calculée à la fin de l'itération, afin de modifier, au besoin, le planning des itérations suivantes. En entreprise, cela permet en outre au client de changer les priorités des tâches, et d'avoir un état d'avancement général du projet (en pourcentage).

\subsection[User stories]{User stories}
Le travail de programmation sera divisé en \emph{user stories} comme suit:\\

\begin{center}
\begin{tabular}{|p{4em}|p{13em}|p{13em}|p{8em}|}
\hline
1 & \multicolumn{2}{|p{26em}|}{\textbf{En tant qu'utilisateur, je veux un cache Web local}} & \emph{Points: }5 \\ 
\hline
\multicolumn{4}{|p{38em}|}{Cache web local sur port 8080, revoi des requêtes sur la cible si l'objet n'est pas en cache} \\
\hline
\multicolumn{2}{|p{19em}|}{\emph{Priorité business:} Haut } & \multicolumn{2}{|p{19em}|}{\emph{Effort:} Haut} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{4em}|p{13em}|p{13em}|p{8em}|}
\hline
2 & \multicolumn{2}{|p{26em}|}{\textbf{En tant qu'utilisateur, je veux que le cache soit persistant}} & \emph{Points: }7 \\  
\hline
\multicolumn{4}{|p{38em}|}{\begin{itemize} \item Stocque les objets sur disque dans SQLite \item le cache doit être nettoyé quand la limite de place est atteinte ou quand l'objet est présent mais trop vieux. \end{itemize}
} \\
\hline
\multicolumn{2}{|p{19em}|}{\emph{Priorité business:} Haut } & \multicolumn{2}{|p{19em}|}{\emph{Effort:} Bas} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{4em}|p{13em}|p{13em}|p{8em}|}
\hline
3 & \multicolumn{2}{|p{26em}|}{\textbf{En tant que serveur de cache, je veux utiliser des marqueurs de récursion pour le dialogue avec mes pairs}} & \emph{Points: }6 \\  
\hline
\multicolumn{4}{|p{38em}|}{Si la requête originelle contient un marqueur de récursion et que les données sont en cache, répondre. Sinon, la transmettre aux pairs en décrémentant le marqueur de récursion de 1.} \\
\hline
\multicolumn{2}{|p{19em}|}{\emph{Priorité business:} Haut } & \multicolumn{2}{|p{19em}|}{\emph{Effort:} Bas} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{4em}|p{13em}|p{13em}|p{8em}|}
\hline
4 & \multicolumn{2}{|p{26em}|}{\textbf{En tant qu'Administrateur, je veux configurer mon cache à l'aide d'un fichier de configuration}} & \emph{Points: }10 \\  
\hline
\multicolumn{4}{|p{38em}|}{
Le fichier doit contenir au moins les informations suivantes:
\begin{itemize}
\item Liste des caches pairs
\item Port d'écoute
\item Niveau de récursion désiré
\item Règles de fraîcheur - extensions fichiers, temps maximum de fraîcheur...
\end{itemize}
} \\
\hline
\multicolumn{2}{|p{19em}|}{\emph{Priorité business:} Haut } & \multicolumn{2}{|p{19em}|}{\emph{Effort:} Haut} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{4em}|p{13em}|p{13em}|p{8em}|}
\hline
5 & \multicolumn{2}{|p{26em}|}{\textbf{En tant qu'administrateur, je veux conserver les données dans une base externe (MySQL)}} & \emph{Points: }7 \\  
\hline
\multicolumn{4}{|p{38em}|}{
Vérifier que les connecteurs SQLite peuvent facilement être échangés pour des connecteurs MySQL.
} \\
\hline
\multicolumn{2}{|p{19em}|}{\emph{Priorité business:} Bas } & \multicolumn{2}{|p{19em}|}{\emph{Effort:} Bas} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{4em}|p{13em}|p{13em}|p{8em}|}
\hline
6 & \multicolumn{2}{|p{26em}|}{\textbf{En tant qu'Administrateur, je veux conserver les données du cache dans le système de fichiers}} & \emph{Points: }9 \\  
\hline
\multicolumn{4}{|p{38em}|}{
\begin{itemize}
\item Le système de fichiers doit être journalisé et transactionnel (ext3 par exemple)
\item Distribution des objets dans un arbre binaire de profondeur X (paramètrable) avec les deux premiers symboles Hexadécimaux des données ou d'un hash des données comme nom de dossier
\end{itemize}
} \\
\hline
\multicolumn{2}{|p{19em}|}{\emph{Priorité business:} Bas } & \multicolumn{2}{|p{19em}|}{\emph{Effort:} Haut} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{4em}|p{13em}|p{13em}|p{8em}|}
\hline
7 & \multicolumn{2}{|p{26em}|}{\textbf{En tant qu'Administrateur, je veux que le cache utilise les données de mon réseau OSPF pour trouver ses pairs}} & \emph{Points: }13 \\  
\hline
\multicolumn{4}{|p{38em}|}{
Tâche très compliquée techniquement!
\begin{itemize}
\item Nécéssite la mise en place d'un réseau OSPF de test
\item Extraire les données du routeur local à la machine au démarrage du cache
\item Prévoir une entrée dans le fichier de configuration
\item Systèmes à base UNIX uniquement! OSPF pour Windows pas disponible
\end{itemize}
} \\
\hline
\multicolumn{2}{|p{19em}|}{\emph{Priorité business:} Bas } & \multicolumn{2}{|p{19em}|}{\emph{Effort:} Haut} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{4em}|p{13em}|p{13em}|p{8em}|}
\hline
8 & \multicolumn{2}{|p{26em}|}{\textbf{En tant qu'Administrateur, je veux des statistiques d'utilisation du cache}} & \emph{Points: }7 \\  
\hline
\multicolumn{4}{|p{38em}|}{
Les statistiques suivantes seraient interessantes:
\begin{itemize}
\item Niveau de recursion moyen des requêtes
\item Proportion de contenu servi depuis le cache (\emph{hit-rate})
\item Objets les plus consultés
\item Sites les plus consultés
\item Type d'objets les plus demandés
\end{itemize}
} \\
\hline
\multicolumn{2}{|p{19em}|}{\emph{Priorité business:} Bas } & \multicolumn{2}{|p{19em}|}{\emph{Effort:} Haut} \\
\hline
\end{tabular}
\end{center}

\subsection[Notes sur les user stories]{Notes sur les user stories}
Les \emph{user stories} décrites ci-dessus sont estimées à un total de 64 soirées idéales. Il est courant de plannifier plus de points que disponible, pour la raison simple que ces points ne sont qu'une \emph{estimation} de la quantité de travail nécessaire. Il est fort possible qu'une user story soit finalement plus facile à réaliser que prévu.\\
De plus, les user stories incluent des objectifs secondaires, dont la priorité est moindre. Les methodes agiles privilègient la livraison d'un logiciel à temps, même si toutes les fonctionalités ne sont pas terminées. Ainsi, il est possible pour Ingénieurs du Monde d'utiliser le logiciel dans son contexte de déployement réel, même si la \emph{user story} numéro 5 (Sauvegarder les données dans une base MySQL) n'est pas utilisable. En revanche, il est impossible pour eux d'utiliser le logiciel si la \emph{user story} numéro 1 (Un cache web local) n'est pas finie!\\

Les user stories identifiées comme non-cruciales, qui répondent aux objectifs secondaires, seront donc terminées \emph{si le temps le permet}. Il est donc normal d'avoir plus de Points plannifiés que de soirées réelles (pas idéales), mais il faut garantir que les objectifs principaux seront réalisés. Cette différence de priorité est exprimée dans les ``cartes'' des user stories sous la forme de \emph{Priotié Business}. Les priorités hautes sont nécessaires à la réussite du projet (et correspondent aux objectifs principaux), les autres correspondent aux objectifs secondaires et peuvent éventuellement ne pas être réalisées.\\ Bien entendu, l'idéal est qu'elles soient toutes réalisées à temps!


\subsection[Découpage temporel]{Découpage temporel}

Le travail est découpé en plusieures phases temporelles:

\begin{description}
\item[Pré-Etude] (Phase d'analyse) C'est la phase de travail qui vise à produire le présent document. Elle s'étend du 6 Avril au 5 Juin.
\item[Phase de réalisation] La phase de fabrication du logiciel. Cette phase sera planifiée et mise en place en utilisant les méthodes agiles. Ainsi, on découpera la période de réalisation en \emph{itérations}\footnote{Une itération est une periode de temps à la fin duquel on dispose d'un produite livrable, bien que n'ayant pas toutes les fonctionalités requises. Voir glossaire (Section \ref{cha:gloss})}.
\item[Phase de mise en production] Dernière partie de la plannification, elle consiste a finaliser le projet, règler d'éventuels derniers bugs, s'occuper de la distribution du produit, et préparer avec le mandant la mise en production. Cette phase se situe après l'échéance scolaire, mais est néanmoins mentionnée ici dans la mesure ou elle fait partie du projet.
\end{description}

\subsection[Découpage de la phase de réalisation]{Découpage de la phase de réalisation en itérations}
La phase de réalisation du projet, qui s'étend du 29 Juin au 30 Octobre, sera découpée en 4 itérations de 1 mois. Fidèle aux méthodes agiles, un certain nombre de user-stories seront attribuées à chaque iteration en fonction de l'estimation du temps de réalisation, et en commençant par les tâches à priori les plus ``risquées'', c'est a dire les plus critiques ou difficiles a réaliser. L'objectif de cette répartition est de détecter les problèmes le plus vite possible, afin d'avoir un maximum de marge de manoeuvre pour les règler, les contourner ou les éviter.\\
Les itérations ont une \emph{vélocité} de 16 Points (``soirées idéales'').

\subsection[Assignation des user stories aux itérations]{Assignation des user stories aux differentes itérations}

Comme décrit précédemment, les user stories les plus risquées devront être traitées en priorité, afin de se garantir une plus grande marge de manoeuvre face aux problèmes éventuels.

\paragraph{Itération 1}
Le thème de cette première itération est ``Créer un cache web persistant'':
\begin{itemize}
\item User story 1 (\emph{En tant qu'utilisateur je veux un cache Web local})
\item User story 2 (\emph{En tant qu’utilisateur, je veux que le cache soit persistant})
\end{itemize}
Cette itération comptabilise 12 points idéaux. C'est moins que la \emph{vélocité}, mais elle devra en outre prendre en compte le temps de mise en place du projet, de l'environment de developpment et de celui de test.

\paragraph{Itération 2}
Cette seconde itération a pour but de rendre le cache ``intelligent et configurable'':
\begin{itemize}
\item User story 3 (\emph{En tant que serveur de cache, je veux utiliser des marqueurs de récursion pour le dialogue avec mes pairs})
\item User story 4 (\emph{En tant qu’Administrateur, je veux configurer mon cache à l’aide d’un fichier de configuration})
\end{itemize}
La difficulté réside ici dans l'implémentation de la logique du cache, c'est le coeur du problème. Cependant, l'environment est déjà en place et le programmeur familiarisé avec le code existant.

\paragraph{Itération 3}
Ici, l'iteration s'occupe d'un objectif secondaire, ``Diversifier la sauvegarde des données'':
\begin{itemize}
\item User story 5 (\emph{En tant qu’administrateur, je veux conserver les données dans une base externe MySQL})
\item User story 6 (\emph{En tant qu’Administrateur, je veux conserver les données du cache dans le système de fichiers})
\end{itemize}
Première itération consacrée aux objectifs secondaires, facultatifs. On prendra garde aux coûts en performance des systèmes de sauvegarde.

\paragraph{Itération 4}
D'autres objectifs secondaires, axés sur les ``fonctionnalités supplémentaires'':
\begin{itemize}
\item User story 7 (\emph{En tant qu’Administrateur, je veux que le cache utilise les données de mon réseau OSPF pour trouver ses pairs})
\item User story 8 (\emph{En tant qu’Administrateur, je veux des statistiques d’utilisation de mon cache})
\end{itemize}
La difficulté sera principalement de mettre en place un réseau de test OSPF.

\section[Échéancier]{Échéancier}

\includegraphics[angle=90,width=120mm,height=220mm]{gantt.png}

\chapter[Conclusion]{Conclusion}

\section[Remerciements]{Remerciements}

Tout d'abord, merci à mon conseiller le Dr. Zysman pour le temps qu'il a investi et la patience dont il a su faire preuve à mon égard.\\

J'aimerai aussi remercier le Dr. Ullmann et toute l'équipe d'Ingénieurs du Monde pour l'interêt et le serieux qu'ils ont accordé à ce projet. Il est intimidant de défendre un projet d'études devant un tel nombre de Docteurs \emph{ès} Sciences dans des domaines divers, mais tous ont sû être rassurants et encourageants lors de nos échanges.\\

De même, je tiens à remercier également mon collègue et camarade Oliver Amblet pour son aide lors de l'estimation des tâches et du découpage du planning. Chef de projet dans nos bureaux de Lausanne, Oliver à su me faire profiter de son experience et de ses conseils pour la plannification, et m'a ainsi permis d'éviter plusieurs pièges courants, notemment de sur-spécifier en définissant des user-stories trop ciblées, et de faire des itérations trop petites, piège facile quand on a l'habitude de travailler à plein temps sur un projet et non pas à temps partiel comme c'est le cas ici.\\

Finalement, un grand merci au Dr. Daniel Siemaszko, de l'Institut Royal de Technologies de Stockholm. Ami de longue date, Daniel a eu l'amabilité de jetter un oeil critique, fruit de sa longue experience en écriture de rapports scientifiques, sur cette pré-étude en général et sur mon utilisation de LaTeX en particulier.

\section[Pourquoi ce projet?]{Pourquoi ce projet?}
Ce projet de recherche permet d'explorer de nombreux aspects interessants de l'informatique, et non le seul aspect technique auquel un programmeur est le plus souvent confronté.\\\\

Dans notre bulle occidentale largement interconnectée ou l'information circule rapidement en utilisant des technologies de pointes, très chère, le programmeur moderne perd souvent de vue la nécessité d'adapter les algorithmes et les procédés à de infrastructures dont les limitations matérielles sont plus contraignantes, comme celles rencontrées les plus souvent dans les pays en voie de développment. Cette barrière économique et psychologie est un énorme frein au développment de réseaux informatiques dans ces régions, qui ne disposent pas des moyens financiers nécéssaires à la mise à niveau occidental de leurs infrastructures, et pour lesquelles les solutions ``astucieuses'' en occident ne sont pas adaptées.\\

Un système de cache distribué adapté à cette configuration n'existe pas, à ma connaissance, et le fait d'en inventer un de toutes pièces représente un défi de taille qu'il me plaît de relever.\\

Employé dans une société multinationale dont les produits s'addressent à d'autres multinationales prêtes à dépenser d'importantes sommes d'argent pour aquièrir des technologies très ``pointues'', ce projet est pour moi une opportunité de penser differement, et de laisser une part de culot et de créativité à ma conception logicelle. Avec le concours d'Ingénieurs du Monde, ce logiciel pourra je l'espère se voir déployer autre part que sur un réseau de test, et surtout répondre au besoin de personnes qui un jour, écriront à leur tour un rapport de pré-étude en vue de l'obtention de leur diplôme d'ingénieurs.\\

Ce travail, purement logiciel, n'est qu'une petite partie des technologies nécessaires à la mise en place d'un réseau internet. J'espère pouvoir continer à contribuer, dans la mesure de mes capacités, à la mise en place des autres ``briques'' nécessaires au déployement d'un réseau WiFi à grande échelle: conception d'antennes plus efficaces, dessin des mâts, analyse de terrain pour déterminer les meilleurs emplacements, étude des besoins \emph{hardware} de chaque antenne, analyse des procédés de refroidissement des machines, des besoins en alimentation éléctrique\ldots Quantité de problèmes restent à résoudre!\\\\
Le défi est passionnant.


% *** BIBLIOGRAPHIE
\chapter[Exploitation de sources bibliographiques]{Exploitation de sources bibliographiques}
\section [Webographie]{Webographie}
\label{cha:webo}
\begin{itemize}
\item Ingénieurs du Monde, ``Ingénieurs du Monde''\\ \url{http://www.ingenieursdumonde.org/} (Page consultée le 1er Juin 2009)
\item Weijand R\&D Consultancy BV, ``10 Euro dish with biquad feeder''\\ \url{http://www.weijand.nl/wifi/} (page consultée le 1er Juin 2009).
\item The Python foundation, ``Python documentation''\\ \url{http://www.python.org/doc/} (page consultée fréquemment... mais pour les besoins de la référence, en date du 1er Juin 2009).
\item The squid-cache.org team, ``Squid-Cache.org''\\ \url{http://www.squid-cache.org} (page consultée le 1er Juin 2009)
\item The Dijjer team, ``Dijjer''\\ \url{http://code.google.com/p/dijjer/} (page consultée le 1er Juin 2009)
\item Tim Love (And the Cambridge University Engineering Dept.), ``Text Processing using LaTeX''\\ \url{http://www.eng.cam.ac.uk/help/tpl/textprocessing/} (page consultée le 1er Juin 2009)
\item BitTorrent Inc., ``What Is Bittorrent'' \\ \url{http://www.bittorrent.com/btusers/what-is-bittorrent} (page consultée le 1er Juin 2009)
\item The SQLite.org team, ``SQLite'' \\ \url{http://www.sqlite.org} (page consultée le 1er Juin 2009)
\end{itemize}

\section[Bibliographie]{Bibliographie}
\label{cha:biblio}

\begin{itemize}
\item Mike Cohn, \emph{Agile estimating and planning}, Pearson Education Inc., 2006.
\item Mark Summerfield, \emph{Programming in Python 3: A Complete Introduction to the Python Language}, Addison-Wesley Professional, Décembre 2008.
\item Guido van Rossum, and Fred L. Drake, Jr., \emph{An Introduction to Python (version 2.5)}, Network Theory Ltd, Novembre 2006.
\item John Goerzen, \emph{Foundations of Python Network Programming}, Apress Inc, Août 2004.
\item Tarek Ziadé, \emph{Expert Python Programming}, Packt Publishing, Septembre 2008.
\end{itemize}

% *** GLOSSAIRE
\chapter[Glossaire]{Glossaire}
\label{cha:gloss}
\begin{description}

\item[ACID] Acronyme Anglais de \emph{Atomicity, Consistency, Isolation, Durability} (Atomicité, Consistence, Isolation, Durabilité). Propriétés garantissant qu'une transaction de base de données soit effectuée de manière sûres (sans pertes de données, sans collisions).

\item[Bande passante] Quantité de données transmises en un temps donné. Typiquement exprimée en kilo bits (kb) par seconde (kb/s), ou en mégabits (mb) par seconde (mb/s).

\item[Bittorrent] Protocole spécialisé dans l'échange de fichiers entre un grand nombre de personnes. Bittorrent permet à ses utilisateurs de publier un descriptif des fichiers qu'ils souhaitent échanger sur un serveur dédié (un \emph{tracker} Bittorrent). Chaque utilisateur se connecte au \emph{tracker}, choisis les fichiers qu'il souhaite obtenir, et publie la liste des fichiers qu'il souhaite distribuer.\\ Lors du téléchargement à proprement parler, les fichiers sont découpés en petits morceaux de quelques ko (kilo octets). Chaque utilisateur se connecte alors aux utilisateurs qui ont annoncé possèder tel ou tel morceau de fichier, et le télécharge directement depuis la machine de l'autre. Avantage: quand je télécharge un fichier, je télécharge en fait des morceaux de fichier depuis plusieurs autres utlisateurs à la fois. Bittorrent vérifie leur intégrité et recompose le fichier une fois tous ses morceaux récupérés.

\item[Cache] Un \emph{Cache} en informatique est un lieu (en mémoire) de stockage temporaire du duplicata d'une information considérée trop chère en ressources à récupérer à nouveau ou à recalculer. Il existe quantité d'endroits où des données sont \emph{cachées} dans un ordinateur moderne (processeur, périphériques réseau, cartes son, disques durs\ldots). Dans le cadre de ce travail, \emph{cache} a toujours le sens de \emph{cache réseau}. Il s'agit d'un système permettant le stockage temporaire de pages internet et de contenu assimilé, telles que images, feuilles de style, scripts, objets multimédias, afin d'accélérer l'affichage de l'information la seconde fois qu'un utilisateur demandera le même objet. \\ Ainsi, si deux personnes, sur deux ordinateurs différents partageant le même \emph{cache} accèdent à la même page internet de façon séquentielle, le premier utilisateur reçevra la page depuis le site originel (vraisememblablement à distance), alors que le second, demandant la même page, recevra le contenu depuis le \emph{cache}. Le cache aura intercepté la demande du premier utilisateur et stocké le résultat (\emph{mis en cache}). Le second utilisateur aura donc vu la page s'afficher beaucoup plus vite que le premier, étant donné que les données étaient locales au réseau dont l'utilisateur fait parti.

\item [Gateway] Mot Anglais signifiant ``Portail''. Un ordinateur \emph{gateway} est un ordinateur appartenant à deux réseaux différents, qui utilisent potentiellement deux protocoles différents, et qui permet aux membres des deux réseaux de communiquer entre eux. C'est la porte par laquelle les deux réseaux communiquent.

\item[Niveau de récursion] Le niveau de récursion est ici utilisé au sens de la théorie des graphes, c'est a dire, en partant d'un noeud N appartenant au graphe G, le niveau de récursion est la profondeur d'exploration de l'arbre recouvrant de G ayant N pour racine. Plus généralement, la récursion est le fait pour une fonction informatique de s'appeler elle-même. Dans notre cas, la fonction en question est la fonction de transmission de l'information. Ainsi, une fois appliquée à un noeud ``père'' le noeud va lui-même appeler cette fonction sur ses ``fils'', qui eux-même l'appliqueront à leurs ``petits-fils'', et ainsi de suite.

\item[Temps de latence] Aussi appelé \emph{lag}, le temps de latence désigne ici le temps écoulé entre l'émission d'une requête et la réception de la réponse correspondante par le serveur intérrogé. Plus généralement, le temps de latence désigne le temps écoulé entre un évenement et le début de la réaction à celui-ci.

\item[OSPF] Acronyme Anglais de \emph{Open Shortest Path First}. Protocole de routage réseau ou chaque noeud (routeur) établit une carte d'adjacence avec ses voisins, et la leur transmet. Il reçoit a son tour la carte d'ajacence de ses voisins, ce qui lui permet d'avoir une vision globale du réseau auquel il appartient. Le protocole lui permet ensuite d'envoyer un message à un noeud quelconque de façon efficace, en appliquand l'algorithme de Djikstra (pour trouver le chemin le plus court entre deux points dans un graphe non orienté).

\item[Overhead] De l'Anglais, litteralement ``Au dessus de la tête''. Faible surconsommation de ressources au profit d'un avantage quelconque. Un \emph{overhead} n'est donc pas considéré comme une perte, mais comme un sacrifice mesuré. On parle par exemple de l'\emph{overhead} d'un protocole réseau qui sacrifierai un peu de temps de calcul afin de garantir l'intégrité des données. Encore, un language de programmation (ici, Python) peut sacrifier un peu de performances au profit de la lisibilité du code source ou de la flexibilité de la syntaxe.

\item[User stories] De l'Anglais, ``histoires utilisateur''. Unité de base pour la découpe et la répartition du travail dans les équipes utilisant les methodologies agiles. Une \emph{user story} est composée des éléments suivants:
\begin{itemize}
\item Un titre, reprenant un acteur des cas d'utilisation: \emph{As an actor, I want...}
\item Un numero d'identification. Lors de gros travaux, il n'est pas rare d'avoir plusieures centaines de \emph{user stories}. Les numéroter permet de les classifier et les réferencer de façon efficace.
\item L'estimation de la difficulté de la tâche
\item L'estimation de la priorité de la tâche
\end{itemize}
Les user stories sont découpées plus finement en tâches au début de l'itération où le travail qu'elles représentent est commencé. Typiquement, les tâches sont ensuites réparties entre les programmeurs à leur bon vouloir, chaqun s'attribuant la tâche qui lui ``plaît'' le plus ou celle pour laquelle il se considère le plus compétent. A la fin d'une tâche, le programmeur choisi sa tâche suivante, jusqu'à ce qu'il ne reste plus de tâches pour l'itération courante. Cet artifice permet de découper agréablement la vision que chaque membre de l'équipe se fait du projet: le chef de projet s'occupe d'assigner les user stories aux differentes équipes, sans se soucier des détails techniques. Les équipes se concentrent sur les tâches en gèrant elles-mêmes la façon dont elles sont réparties.

\end{description}

\end{document}
